<!doctype html public "-//W3C//DTD HTML 4.0 Transitional//EN" "http://www.w3.org/TR/REC-html40/loose.dtd">
<html>
<!-- Generated from TeX source by tex2page, v 4o, 
     (c) Dorai Sitaram, http://www.cs.rice.edu/~dorai/tex2page -->
<head>
<title>
Structure and Interpretation 
of Computer Programs
</title>
<link rel="stylesheet" type="text/css" href="book-Z-C.css" title=default>
<meta name=robots content="noindex,follow">
</head>
<body>

<p><div class=navigation>[Go to <span><a href="book.html">first</a>, <a href="book-Z-H-11.html">previous</a></span><span>, <a href="book-Z-H-13.html">next</a></span> page<span>; &nbsp;&nbsp;</span><span><a href="book-Z-H-4.html#%_toc_start">contents</a></span><span><span>; &nbsp;&nbsp;</span><a href="book-Z-H-38.html#%_index_start">index</a></span>]</div><p>

<a name="%_sec_1.3"></a>
<h2><a href="book-Z-H-4.html#%_toc_%_sec_1.3">1.3&nbsp;&nbsp;Formulating Abstractions with Higher-Order Procedures</a></h2><p>

<p>


We have seen that procedures are, in effect, abstractions that describe
compound operations on numbers independent of the particular numbers.
For example, when we<p>


<p><p><tt><a name="%_idx_962"></a>(define&nbsp;(cube&nbsp;x)&nbsp;(*&nbsp;x&nbsp;x&nbsp;x))<br>
</tt><p><p>
we are not talking about the cube of a particular number, but rather
about a method for obtaining the cube of any number.  Of course we
could get along without ever defining this procedure, by
always writing expressions such as<p>

<p><p><tt>(*&nbsp;3&nbsp;3&nbsp;3)<br>
(*&nbsp;x&nbsp;x&nbsp;x)<br>
(*&nbsp;y&nbsp;y&nbsp;y)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<br>
</tt><p><p>
and never mentioning <tt>cube</tt> explicitly.  This would place us at a
serious disadvantage, forcing us to work always at the level of the
particular operations that happen to be primitives in the language
(multiplication, in this case) rather than in terms of higher-level
operations.  Our programs would be able to compute cubes, but our
language would lack the ability to express the concept of cubing.  One
of the things we should demand from a powerful programming language is
the ability to build abstractions by assigning names to common
patterns and then to work in terms of the abstractions directly.
Procedures provide this ability.  This is why all but the most
primitive programming languages include mechanisms for defining
procedures.<p>

Yet even in numerical processing we will be severely limited in our
ability to create abstractions if we are restricted to procedures
whose parameters must be numbers.  Often the same programming pattern
will be used with a number of different procedures.  To express such
patterns as concepts, we will need to construct procedures that can
accept procedures as arguments or return procedures as values.
Procedures that manipulate procedures are called <a name="%_idx_964"></a><em>higher-order
procedures</em>.  This section shows how higher-order procedures can serve
as powerful abstraction mechanisms, vastly increasing the expressive
power of our language.<p>

<a name="%_sec_1.3.1"></a>
<h3><a href="book-Z-H-4.html#%_toc_%_sec_1.3.1">1.3.1&nbsp;&nbsp;Procedures as Arguments</a></h3><p>


<a name="%_idx_966"></a><a name="%_idx_968"></a>

Consider the following three procedures.  The first computes the sum
of the integers from <tt>a</tt> through <tt>b</tt>:<p>

<p><p><tt><a name="%_idx_970"></a>(define&nbsp;(sum-integers&nbsp;a&nbsp;b)<br>
&nbsp;&nbsp;(if&nbsp;(&gt;&nbsp;a&nbsp;b)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;0<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(+&nbsp;a&nbsp;(sum-integers&nbsp;(+&nbsp;a&nbsp;1)&nbsp;b))))<br>
</tt><p><p>
The second computes the sum of the cubes of the integers in the given range:<p>

<p><p><tt><a name="%_idx_972"></a>(define&nbsp;(sum-cubes&nbsp;a&nbsp;b)<br>
&nbsp;&nbsp;(if&nbsp;(&gt;&nbsp;a&nbsp;b)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;0<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(+&nbsp;(cube&nbsp;a)&nbsp;(sum-cubes&nbsp;(+&nbsp;a&nbsp;1)&nbsp;b))))<br>
</tt><p><p>
The third computes the sum of a sequence of terms in the
series
<p><div align=left><img src="ch1-Z-G-26.gif" border="0"></div><p>
which converges to <img src="book-Z-G-D-9.gif" border="0">/8 (very slowly):<a name="call_footnote_Temp_90" href="#footnote_Temp_90"><sup><small>49</small></sup></a><p>

<p><p><tt><a name="%_idx_978"></a>(define&nbsp;(pi-sum&nbsp;a&nbsp;b)<br>
&nbsp;&nbsp;(if&nbsp;(&gt;&nbsp;a&nbsp;b)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;0<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(+&nbsp;(/&nbsp;1.0&nbsp;(*&nbsp;a&nbsp;(+&nbsp;a&nbsp;2)))&nbsp;(pi-sum&nbsp;(+&nbsp;a&nbsp;4)&nbsp;b))))<br>
</tt><p><p><p>

These three procedures clearly share a common underlying pattern.
They are for the most part identical, differing only in the name of
the procedure, the function of <tt>a</tt> used to compute the term to be added,
and the function that provides the next value of <tt>a</tt>.  We could generate
each of the procedures by filling in slots in the same template:<p>

<p><p><tt>(define&nbsp;(&lt;<em>name</em>&gt;&nbsp;a&nbsp;b)<br>
&nbsp;&nbsp;(if&nbsp;(&gt;&nbsp;a&nbsp;b)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;0<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(+&nbsp;(&lt;<em>term</em>&gt;&nbsp;a)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(&lt;<em>name</em>&gt;&nbsp;(&lt;<em>next</em>&gt;&nbsp;a)&nbsp;b))))<br>
</tt><p><p><p>

<a name="%_idx_980"></a>The presence of such a common pattern is strong evidence that there is
a useful abstraction waiting to be brought to the surface.  Indeed,
mathematicians long ago identified the abstraction of
<a name="%_idx_982"></a><a name="%_idx_984"></a><em>summation of a series</em> and invented ``sigma
<a name="%_idx_986"></a><a name="%_idx_988"></a>notation,'' for example<p>

<p><div align=left><img src="ch1-Z-G-27.gif" border="0"></div><p><p>

to express this concept.  The power of sigma notation is that it
allows mathematicians to deal with the concept of summation
itself rather than only with particular sums -- for example, to
formulate general results about sums that are independent of the
particular series being summed.<p>

Similarly, as program designers, we would like our language to
be powerful enough so that we can write a procedure that expresses the
concept of summation itself rather than only procedures
that compute particular sums.  We can do so readily in our
procedural language by taking the common template shown above and
transforming the ``slots'' into formal parameters:<p>

<p><p><tt><a name="%_idx_990"></a>(define&nbsp;(sum&nbsp;term&nbsp;a&nbsp;next&nbsp;b)<br>
&nbsp;&nbsp;(if&nbsp;(&gt;&nbsp;a&nbsp;b)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;0<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(+&nbsp;(term&nbsp;a)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(sum&nbsp;term&nbsp;(next&nbsp;a)&nbsp;next&nbsp;b))))<br>
</tt><p><p>
Notice that <tt>sum</tt> takes as its arguments the lower and upper bounds
<tt>a</tt>&nbsp;and&nbsp;<tt>b</tt> together with the procedures <tt>term</tt> and <tt>next</tt>.
We can use <tt>sum</tt> just as we would any procedure.  For example, we can
use it (along with a procedure <tt>inc</tt> that increments its argument by 1)
to define <tt>sum-cubes</tt>:<p>

<p><p><tt><a name="%_idx_992"></a>(define&nbsp;(inc&nbsp;n)&nbsp;(+&nbsp;n&nbsp;1))<br>
<a name="%_idx_994"></a>(define&nbsp;(sum-cubes&nbsp;a&nbsp;b)<br>
&nbsp;&nbsp;(sum&nbsp;cube&nbsp;a&nbsp;inc&nbsp;b))<br>
</tt><p><p>
Using this, we can compute the sum of the cubes of the integers from 1
to 10:<p>


<p><p><tt>(sum-cubes&nbsp;1&nbsp;10)<br>
<i>3025</i><br>
</tt><p><p>
With the aid of an identity procedure to compute the term, we can define
<tt>sum-integers</tt> in terms of <tt>sum</tt>:<p>


<p><p><tt><a name="%_idx_996"></a>(define&nbsp;(identity&nbsp;x)&nbsp;x)<br>
<br>
<a name="%_idx_998"></a>(define&nbsp;(sum-integers&nbsp;a&nbsp;b)<br>
&nbsp;&nbsp;(sum&nbsp;identity&nbsp;a&nbsp;inc&nbsp;b))<br>
</tt><p><p>
Then we can add up the integers from 1 to 10:<p>


<p><p><tt>(sum-integers&nbsp;1&nbsp;10)<br>
<i>55</i><br>
</tt><p><p>
We can also define <tt>pi-sum</tt> in the same way:<a name="call_footnote_Temp_91" href="#footnote_Temp_91"><sup><small>50</small></sup></a><p>


<p><p><tt><a name="%_idx_1000"></a>(define&nbsp;(pi-sum&nbsp;a&nbsp;b)<br>
&nbsp;&nbsp;(define&nbsp;(pi-term&nbsp;x)<br>
&nbsp;&nbsp;&nbsp;&nbsp;(/&nbsp;1.0&nbsp;(*&nbsp;x&nbsp;(+&nbsp;x&nbsp;2))))<br>
&nbsp;&nbsp;(define&nbsp;(pi-next&nbsp;x)<br>
&nbsp;&nbsp;&nbsp;&nbsp;(+&nbsp;x&nbsp;4))<br>
&nbsp;&nbsp;(sum&nbsp;pi-term&nbsp;a&nbsp;pi-next&nbsp;b))<br>
</tt><p><p>
Using these procedures, we can compute an approximation to 
<img src="book-Z-G-D-9.gif" border="0">:<p>


<p><p><tt>(*&nbsp;8&nbsp;(pi-sum&nbsp;1&nbsp;1000))<br>
<i>3.139592655589783</i><br>
</tt><p><p><p>


Once we have <tt>sum</tt>, we can use it as a building block in
formulating further concepts.  For instance, the <a name="%_idx_1002"></a>definite integral of a
function <em>f</em> between the limits <em>a</em> and <em>b</em> can be approximated
numerically using the formula
<p><p><div align=left><img src="ch1-Z-G-28.gif" border="0"></div><p>
for small values of <em>d</em><em>x</em>.  We can express this directly as a
procedure:<p>

<p><p><tt><a name="%_idx_1004"></a>(define&nbsp;(integral&nbsp;f&nbsp;a&nbsp;b&nbsp;dx)<br>
&nbsp;&nbsp;(define&nbsp;(add-dx&nbsp;x)&nbsp;(+&nbsp;x&nbsp;dx))<br>
&nbsp;&nbsp;(*&nbsp;(sum&nbsp;f&nbsp;(+&nbsp;a&nbsp;(/&nbsp;dx&nbsp;2.0))&nbsp;add-dx&nbsp;b)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;dx))<br>
(integral&nbsp;cube&nbsp;0&nbsp;1&nbsp;0.01)<br>
<i>.24998750000000042</i><br>
(integral&nbsp;cube&nbsp;0&nbsp;1&nbsp;0.001)<br>
<i>.249999875000001</i><br>
</tt><p><p>
(The exact value of the integral of <tt>cube</tt> between 0 and 1 is 1/4.)<p>

<p><a name="%_thm_1.29"></a>
<b>Exercise 1.29.</b>&nbsp;&nbsp;<a name="%_idx_1006"></a>Simpson's Rule is a more accurate method of numerical integration than
the method illustrated above.  Using Simpson's Rule, the integral of a
function <em>f</em> between <em>a</em> and <em>b</em> is approximated as
<p><div align=left><img src="ch1-Z-G-29.gif" border="0"></div><p><p>

where <em>h</em> = (<em>b</em> - <em>a</em>)/<em>n</em>, for some even integer <em>n</em>, and <em>y</em><sub><em>k</em></sub>  = <em>f</em>(<em>a</em> + <em>k</em><em>h</em>).
(Increasing <em>n</em> increases the accuracy of the approximation.)  Define
a procedure that takes as arguments <em>f</em>, <em>a</em>, <em>b</em>, and <em>n</em> and returns
the value of the integral, computed using Simpson's Rule.
Use your procedure to integrate <tt>cube</tt> between 0 and 1
(with <em>n</em> = 100 and <em>n</em> = 1000), and compare the results to those of the
<tt>integral</tt> procedure shown above.
<p><p>

<p><a name="%_thm_1.30"></a>
<b>Exercise 1.30.</b>&nbsp;&nbsp;<a name="%_idx_1008"></a>The <tt>sum</tt> procedure above generates a linear recursion.  The
procedure can be rewritten so that the sum is performed iteratively.
Show how to do this by filling in the missing expressions in the
following definition:<p>

<p><p><tt>(define&nbsp;(sum&nbsp;term&nbsp;a&nbsp;next&nbsp;b)<br>
&nbsp;&nbsp;(define&nbsp;(iter&nbsp;a&nbsp;result)<br>
&nbsp;&nbsp;&nbsp;&nbsp;(if&nbsp;&lt;<em>??</em>&gt;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&lt;<em>??</em>&gt;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(iter&nbsp;&lt;<em>??</em>&gt;&nbsp;&lt;<em>??</em>&gt;)))<br>
&nbsp;&nbsp;(iter&nbsp;&lt;<em>??</em>&gt;&nbsp;&lt;<em>??</em>&gt;))<br>
</tt><p><p>
<p><p>

<p><a name="%_thm_1.31"></a>
<b>Exercise 1.31.</b>&nbsp;&nbsp;
<a name="%_idx_1010"></a><br>a.&nbsp;&nbsp;The <tt>sum</tt> procedure is only the simplest of a vast number of
similar abstractions that can be captured as higher-order procedures.<a name="call_footnote_Temp_95" href="#footnote_Temp_95"><sup><small>51</small></sup></a>  Write an analogous procedure
called <tt>product</tt> that returns the product of the values of a
function at points over a given range.
Show how to define <a name="%_idx_1012"></a><tt>factorial</tt> in terms of
<tt>product</tt>.  Also use <tt>product</tt> to compute approximations to
<a name="%_idx_1014"></a><img src="book-Z-G-D-9.gif" border="0"> using the formula<a name="call_footnote_Temp_96" href="#footnote_Temp_96"><sup><small>52</small></sup></a>
<p><div align=left><img src="ch1-Z-G-30.gif" border="0"></div><p><p>

b.&nbsp;&nbsp;If your <tt>product</tt>
procedure generates a recursive process, write one that generates
an iterative process.
If it generates an iterative process, write one that generates
a recursive process.

<p><p>

<p><a name="%_thm_1.32"></a>
<b>Exercise 1.32.</b>&nbsp;&nbsp;<a name="%_idx_1018"></a><a name="%_idx_1020"></a><a name="%_idx_1022"></a>a. Show that <tt>sum</tt> and <tt>product</tt>
(exercise&nbsp;<a href="#%_thm_1.31">1.31</a>) are both special cases of a still more
general notion called <tt>accumulate</tt> that combines a collection of
terms, using some general accumulation function:<p>

<p><p><tt>(accumulate&nbsp;combiner&nbsp;null-value&nbsp;term&nbsp;a&nbsp;next&nbsp;b)<br>
</tt><p><p>
<tt>Accumulate</tt> takes as arguments the same term and range
specifications as <tt>sum</tt> and <tt>product</tt>, together with a <tt>combiner</tt>
procedure (of two arguments) that specifies how the current
term is to be combined with the accumulation of the preceding terms
and a <tt>null-value</tt> that specifies what base value to use
when the terms run out.  Write <tt>accumulate</tt>
and show how <tt>sum</tt> and <tt>product</tt> can both
be defined as simple calls to <tt>accumulate</tt>.<p>

<p><p>b. If your <tt>accumulate</tt>
procedure generates a recursive process, write one that generates
an iterative process.
If it generates an iterative process, write one that generates
a recursive process.

<p><p>

<p><a name="%_thm_1.33"></a>
<b>Exercise 1.33.</b>&nbsp;&nbsp;<a name="%_idx_1024"></a>You can obtain an even more general version of <tt>accumulate</tt>
(exercise&nbsp;<a href="#%_thm_1.32">1.32</a>) by introducing the notion of a <a name="%_idx_1026"></a><em>filter</em> on the terms to be combined.  That is, combine only those
terms derived from values in the range that satisfy a specified
condition.  The resulting <tt>filtered-accumulate</tt> abstraction takes
the same arguments as accumulate, together with an additional
predicate of one argument that specifies the filter.  Write <tt>filtered-accumulate</tt> as a procedure.  Show how to express the
following using <tt>filtered-accumulate</tt>:<p>

<p><p>a. the sum of the squares of the prime numbers in the interval <em>a</em> to
<em>b</em> (assuming that you have a <tt>prime?</tt> predicate already written)<p>

<p><p>b. the product of all the positive integers less than <em>n</em>
<a name="%_idx_1028"></a>that are relatively prime to&nbsp;<em>n</em> (i.e., all positive integers
<em>i</em> &lt; <em>n</em> such that  <em>G</em><em>C</em><em>D</em>(<em>i</em>,<em>n</em>) = 1).

<p><p>

<a name="%_sec_1.3.2"></a>
<h3><a href="book-Z-H-4.html#%_toc_%_sec_1.3.2">1.3.2&nbsp;&nbsp;Constructing Procedures Using <tt>Lambda</tt></a></h3><p>


<p>

In using <tt>sum</tt> as in section&nbsp;<a href="#%_sec_1.3.1">1.3.1</a>,
it seems terribly awkward to have to define trivial procedures such as
<tt>pi-term</tt> and <tt>pi-next</tt> just so we can use them as arguments to
our higher-order procedure.  Rather than define <tt>pi-next</tt> and <tt>pi-term</tt>, it would be more convenient
to have a way to directly specify ``the procedure that returns its
input incremented by 4'' and ``the procedure that returns the
reciprocal of its input times its input plus 2.''  We can do this by
introducing the special form <tt>lambda</tt>, which creates procedures.
Using <tt>lambda</tt> we can describe what we want as<p>

<p><p><tt>(lambda&nbsp;(x)&nbsp;(+&nbsp;x&nbsp;4))<br>
</tt><p><p>
and <p>

<p><p><tt>(lambda&nbsp;(x)&nbsp;(/&nbsp;1.0&nbsp;(*&nbsp;x&nbsp;(+&nbsp;x&nbsp;2))))<br>
</tt><p><p>
Then our <tt>pi-sum</tt> procedure can be expressed without defining any
auxiliary procedures as<p>

<p><p><tt><a name="%_idx_1030"></a>(define&nbsp;(pi-sum&nbsp;a&nbsp;b)<br>
&nbsp;&nbsp;(sum&nbsp;(lambda&nbsp;(x)&nbsp;(/&nbsp;1.0&nbsp;(*&nbsp;x&nbsp;(+&nbsp;x&nbsp;2))))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;a<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(lambda&nbsp;(x)&nbsp;(+&nbsp;x&nbsp;4))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;b))<br>
</tt><p><p><p>

Again using <tt>lambda</tt>, we can write the <tt>integral</tt> procedure
without having to define the auxiliary procedure <tt>add-dx</tt>:<p>

<p><p><tt><a name="%_idx_1032"></a>(define&nbsp;(integral&nbsp;f&nbsp;a&nbsp;b&nbsp;dx)<br>
&nbsp;&nbsp;(*&nbsp;(sum&nbsp;f<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(+&nbsp;a&nbsp;(/&nbsp;dx&nbsp;2.0))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(lambda&nbsp;(x)&nbsp;(+&nbsp;x&nbsp;dx))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;b)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;dx))<br>
</tt><p><p><p>

<a name="%_idx_1034"></a><a name="%_idx_1036"></a><a name="%_idx_1038"></a><a name="%_idx_1040"></a><a name="%_idx_1042"></a>In general, <tt>lambda</tt> is used to create procedures in the same way as
<tt>define</tt>, except that <a name="%_idx_1044"></a>no name is specified for the procedure:<p>

<p><p><tt>(lambda&nbsp;(&lt;<em>formal-parameters</em>&gt;)&nbsp;&lt;<em>body</em>&gt;)<br>
</tt><p><p>
The resulting procedure is just as much a procedure as one that is
created using <tt>define</tt>.  The only difference is that it has not
been associated with any name in the environment.  In fact,<p>

<a name="%_idx_1046"></a><p><p><tt>(define&nbsp;(plus4&nbsp;x)&nbsp;(+&nbsp;x&nbsp;4))<br>
</tt><p><p>
is equivalent to<p>

<p><p><tt>(define&nbsp;plus4&nbsp;(lambda&nbsp;(x)&nbsp;(+&nbsp;x&nbsp;4)))<br>
</tt><p><p>
We can read a <tt>lambda</tt> expression as follows:
<p><p><tt>&nbsp;&nbsp;&nbsp;&nbsp;(lambda&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(x)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(+&nbsp;&nbsp;&nbsp;&nbsp;x&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;4))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<img src="book-Z-G-D-16.gif" border="0">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<img src="book-Z-G-D-16.gif" border="0">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<img src="book-Z-G-D-16.gif" border="0">&nbsp;&nbsp;&nbsp;&nbsp;<img src="book-Z-G-D-16.gif" border="0">&nbsp;&nbsp;&nbsp;&nbsp;<img src="book-Z-G-D-16.gif" border="0"><br>
&nbsp;the&nbsp;procedure&nbsp;&nbsp;&nbsp;of&nbsp;an&nbsp;argument&nbsp;<tt>x</tt>&nbsp;&nbsp;that&nbsp;adds&nbsp;&nbsp;<tt>x</tt>&nbsp;and&nbsp;4<br>
</tt><p><p>

<a name="%_idx_1048"></a><a name="%_idx_1050"></a><a name="%_idx_1052"></a>Like any expression that has a procedure as its value, a
<tt>lambda</tt> expression can be used as the operator in a combination such as<p>

<p><p><tt>((lambda&nbsp;(x&nbsp;y&nbsp;z)&nbsp;(+&nbsp;x&nbsp;y&nbsp;(square&nbsp;z)))&nbsp;1&nbsp;2&nbsp;3)<br>
<i>12</i><br>
</tt><p><p>
or, more generally, in any context where we would normally use a
procedure name.<a name="call_footnote_Temp_99" href="#footnote_Temp_99"><sup><small>53</small></sup></a><p>

<a name="%_sec_Temp_100"></a>
<h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_100">Using <tt>let</tt> to create local variables</a></h4><p>

<a name="%_idx_1058"></a><a name="%_idx_1060"></a>

Another use of <tt>lambda</tt> is in creating local variables.
We often need local variables in our procedures other than those that have
been bound as formal parameters.  For example, suppose we wish to
compute the function<p>

<p><div align=left><img src="ch1-Z-G-31.gif" border="0"></div><p><p>

which we could also express as
<p><div align=left><img src="ch1-Z-G-32.gif" border="0"></div><p>
In writing a procedure to compute <em>f</em>, we would like to include as
local variables not only <em>x</em> and <em>y</em>  but also the names of
intermediate quantities like <em>a</em> and <em>b</em>.  One way to
accomplish this is to
use an auxiliary procedure to bind the local variables:<p>


<p><p><tt>(define&nbsp;(f&nbsp;x&nbsp;y)<br>
&nbsp;&nbsp;(define&nbsp;(f-helper&nbsp;a&nbsp;b)<br>
&nbsp;&nbsp;&nbsp;&nbsp;(+&nbsp;(*&nbsp;x&nbsp;(square&nbsp;a))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(*&nbsp;y&nbsp;b)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(*&nbsp;a&nbsp;b)))<br>
&nbsp;&nbsp;(f-helper&nbsp;(+&nbsp;1&nbsp;(*&nbsp;x&nbsp;y))&nbsp;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(-&nbsp;1&nbsp;y)))<br>
</tt><p><p><p>

Of course, we could use a <tt>lambda</tt> expression to specify an
anonymous procedure for binding our local variables.  The body of
<tt>f</tt> then becomes a single call to that procedure:<p>


<p><p><tt>(define&nbsp;(f&nbsp;x&nbsp;y)<br>
&nbsp;&nbsp;((lambda&nbsp;(a&nbsp;b)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(+&nbsp;(*&nbsp;x&nbsp;(square&nbsp;a))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(*&nbsp;y&nbsp;b)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(*&nbsp;a&nbsp;b)))<br>
&nbsp;&nbsp;&nbsp;(+&nbsp;1&nbsp;(*&nbsp;x&nbsp;y))<br>
&nbsp;&nbsp;&nbsp;(-&nbsp;1&nbsp;y)))<br>
</tt><p><p>
This construct is so useful that there is a special form called
<tt>let</tt> to make its use more convenient.  Using <tt>let</tt>, the <tt>f</tt>
procedure could be written as<p>


<p><p><tt>(define&nbsp;(f&nbsp;x&nbsp;y)<br>
&nbsp;&nbsp;(let&nbsp;((a&nbsp;(+&nbsp;1&nbsp;(*&nbsp;x&nbsp;y)))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(b&nbsp;(-&nbsp;1&nbsp;y)))<br>
&nbsp;&nbsp;&nbsp;&nbsp;(+&nbsp;(*&nbsp;x&nbsp;(square&nbsp;a))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(*&nbsp;y&nbsp;b)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(*&nbsp;a&nbsp;b))))<br>
</tt><p><p>
<a name="%_idx_1062"></a><a name="%_idx_1064"></a>The general form of a <tt>let</tt> expression is<p>


<p><p><tt>(let&nbsp;((&lt;<em>var<sub>1</sub></em>&gt;&nbsp;&lt;<em>exp<sub>1</sub></em>&gt;)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(&lt;<em>var<sub>2</sub></em>&gt;&nbsp;&lt;<em>exp<sub>2</sub></em>&gt;)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<img src="book-Z-G-D-18.gif" border="0"><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(&lt;<em>var<sub><em>n</em></sub></em>&gt;&nbsp;&lt;<em>exp<sub><em>n</em></sub></em>&gt;))<br>
&nbsp;&nbsp;&nbsp;&lt;<em>body</em>&gt;)<br>
</tt><p><p>
which can be thought of as saying<p>

<table border=0><tr><td valign=top >let </td><td valign=top >&lt;<em>var<sub>1</sub></em>&gt; have the value &lt;<em>exp<sub>1</sub></em>&gt; and</td></tr>
<tr><td valign=top ></td><td valign=top >&lt;<em>var<sub>2</sub></em>&gt; have the value &lt;<em>exp<sub>2</sub></em>&gt; and</td></tr>
<tr><td valign=top ></td><td valign=top ><img src="book-Z-G-D-18.gif" border="0"></td></tr>
<tr><td valign=top ></td><td valign=top >&lt;<em>var<sub><em>n</em></sub></em>&gt; have the value &lt;<em>exp<sub><em>n</em></sub></em>&gt;</td></tr>
<tr><td valign=top >in  </td><td valign=top >&lt;<em>body</em>&gt;
</td></tr></table><p>

The first part of the <tt>let</tt> expression is a list of
name-expression pairs.  When the <tt>let</tt> is evaluated, each name is
associated with the value of the corresponding expression.  The body
of the <tt>let</tt> is evaluated with
these names bound as local variables.  The way this happens is that the <tt>let</tt> expression is interpreted as an alternate syntax for<p>

<p><p><tt>((lambda&nbsp;(&lt;<em>var<sub>1</sub></em>&gt;&nbsp;<tt>...</tt>&lt;<em>var<sub><em>n</em></sub></em>&gt;)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&lt;<em>body</em>&gt;)<br>
&nbsp;&lt;<em>exp<sub>1</sub></em>&gt;<br>
&nbsp;<img src="book-Z-G-D-18.gif" border="0"><br>
&nbsp;&lt;<em>exp<sub><em>n</em></sub></em>&gt;)<br>
</tt><p><p>
No new mechanism is required in the interpreter in order to
provide local variables.  A <a name="%_idx_1066"></a><a name="%_idx_1068"></a><tt>let</tt> expression is simply syntactic sugar for
the underlying <tt>lambda</tt> application.<p>

<a name="%_idx_1070"></a><a name="%_idx_1072"></a>We can see from this equivalence that
the scope of a variable specified by a <tt>let</tt> expression is the body of
the <tt>let</tt>.
This implies that:<p>

<p><ul>
<li><tt>Let</tt> allows one to
bind variables as locally as possible to where they
are to be used.  For example, if the value of <tt>x</tt> is 5,
the value of the expression<p>

<p><p><tt>(+&nbsp;(let&nbsp;((x&nbsp;3))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(+&nbsp;x&nbsp;(*&nbsp;x&nbsp;10)))<br>
&nbsp;&nbsp;&nbsp;x)<br>
</tt><p><p><p>

is 38.  Here, the <tt>x</tt> in the body of the <tt>let</tt> is 3,
so the value of the <tt>let</tt> expression is 33.  On the other hand, the
<tt>x</tt> that is the second argument to the outermost <tt>+</tt> is still&nbsp;5.<p>

<li>The variables' values are computed outside the <tt>let</tt>.
This matters when the expressions that
provide the values for the local variables depend upon
variables having the same names as the local variables themselves.
For example, if the value of <tt>x</tt> is 2, the expression<p>

<p><p><tt>(let&nbsp;((x&nbsp;3)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(y&nbsp;(+&nbsp;x&nbsp;2)))<br>
&nbsp;&nbsp;(*&nbsp;x&nbsp;y))<br>
</tt><p><p>
will have the value 12 because, inside the body of the <tt>let</tt>,
<tt>x</tt> will be 3 and <tt>y</tt> will be 4 (which is the
outer <tt>x</tt> plus 2).
</ul><p><p>


<a name="%_idx_1074"></a><a name="%_idx_1076"></a>Sometimes we can use internal definitions to get the same effect as
with <tt>let</tt>.  For example, we could have defined the procedure <tt>f</tt> above as
<p><p><tt>(define&nbsp;(f&nbsp;x&nbsp;y)<br>
&nbsp;&nbsp;(define&nbsp;a&nbsp;(+&nbsp;1&nbsp;(*&nbsp;x&nbsp;y)))<br>
&nbsp;&nbsp;(define&nbsp;b&nbsp;(-&nbsp;1&nbsp;y))<br>
&nbsp;&nbsp;(+&nbsp;(*&nbsp;x&nbsp;(square&nbsp;a))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(*&nbsp;y&nbsp;b)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(*&nbsp;a&nbsp;b)))<br>
</tt><p><p>
We prefer, however, to use <tt>let</tt> in situations like this
and to use internal <tt>define</tt> only for internal procedures.<a name="call_footnote_Temp_101" href="#footnote_Temp_101"><sup><small>54</small></sup></a><p>

<p><a name="%_thm_1.34"></a>
<b>Exercise 1.34.</b>&nbsp;&nbsp;Suppose we define the procedure<p>

<p><p><tt>(define&nbsp;(f&nbsp;g)<br>
&nbsp;&nbsp;(g&nbsp;2))<br>
</tt><p><p>
Then we have<p>

<p><p><tt>(f&nbsp;square)<br>
<i>4</i><br>
<br>
(f&nbsp;(lambda&nbsp;(z)&nbsp;(*&nbsp;z&nbsp;(+&nbsp;z&nbsp;1))))<br>
<i>6</i><br>
</tt><p><p>
What happens if we (perversely) ask the interpreter to evaluate the
combination <tt>(f f)</tt>?  Explain.
<p><p>

<a name="%_sec_1.3.3"></a>
<h3><a href="book-Z-H-4.html#%_toc_%_sec_1.3.3">1.3.3&nbsp;&nbsp;Procedures as General Methods</a></h3><p>


<a name="%_idx_1078"></a><a name="%_idx_1080"></a>
We introduced compound procedures in
section&nbsp;<a href="book-Z-H-10.html#%_sec_1.1.4">1.1.4</a> as a mechanism for abstracting
patterns of numerical operations so as to make them independent of the
particular numbers involved.  With higher-order procedures, such as
the <tt>integral</tt> procedure of
section&nbsp;<a href="#%_sec_1.3.1">1.3.1</a>, we began to see a more
powerful kind of abstraction: procedures used to express general
methods of computation, independent of the particular functions
involved.  In this section we discuss two more elaborate
examples -- general methods for finding zeros and fixed points of
functions -- and show how these methods can be expressed directly as
procedures.<p>

<a name="%_sec_Temp_103"></a>
<h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_103">Finding roots of equations by the half-interval method</a></h4><p>

<a name="%_idx_1082"></a>
The <em>half-interval method</em> is a simple but powerful technique for
finding roots of an equation <em>f</em>(<em>x</em>) = 0, where <em>f</em> is a continuous
function.  The idea is that, if we are given points <em>a</em> and <em>b</em> such
that <em>f</em>(<em>a</em>) &lt; 0 &lt; <em>f</em>(<em>b</em>), then <em>f</em> must have at least one zero between
<em>a</em> and <em>b</em>.  To locate a zero, let <em>x</em> be the average of <em>a</em> and <em>b</em>
and compute <em>f</em>(<em>x</em>).  If <em>f</em>(<em>x</em>) &gt; 0, then <em>f</em> must have a zero between
<em>a</em> and <em>x</em>.  If <em>f</em>(<em>x</em>) &lt; 0, then <em>f</em> must have a zero between <em>x</em> and
<em>b</em>.  Continuing in this way, we can identify smaller and smaller
intervals on which <em>f</em> must have a zero.  When we reach a point where
the interval is small enough, the process stops.  Since the interval
of uncertainty is reduced by half at each step of the process, the
number of steps required grows as <img src="book-Z-G-D-3.gif" border="0">(<tt>log</tt>( <em>L</em>/<em>T</em>)), where <em>L</em> is the
length of the original interval and <em>T</em> is the error tolerance
(that is, the size of the interval we will consider ``small enough'').
Here is a procedure that implements this strategy:<p>


<p><p><tt><a name="%_idx_1084"></a>(define&nbsp;(search&nbsp;f&nbsp;neg-point&nbsp;pos-point)<br>
&nbsp;&nbsp;(let&nbsp;((midpoint&nbsp;(average&nbsp;neg-point&nbsp;pos-point)))<br>
&nbsp;&nbsp;&nbsp;&nbsp;(if&nbsp;(close-enough?&nbsp;neg-point&nbsp;pos-point)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;midpoint<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(let&nbsp;((test-value&nbsp;(f&nbsp;midpoint)))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(cond&nbsp;((positive?&nbsp;test-value)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(search&nbsp;f&nbsp;neg-point&nbsp;midpoint))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;((negative?&nbsp;test-value)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(search&nbsp;f&nbsp;midpoint&nbsp;pos-point))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(else&nbsp;midpoint))))))<br>
</tt><p><p><p>

We assume that we are initially given the function <em>f</em> together with
points at which its values are negative and positive.  We first
compute the midpoint of the two given points.  Next we check to see if
the given interval is small enough, and if so we simply return the
midpoint as our answer.  Otherwise, we compute as a test value the
value of <em>f</em> at the midpoint.  If the test value is positive, then
we continue the process with a new interval running from the original
negative point to the midpoint.  If the test value is negative, we
continue with the interval from the midpoint to the positive point.
Finally, there is the possibility that the test value is&nbsp;0, in which
case the midpoint is itself the root we are searching for.<p>


To test whether the endpoints are ``close enough'' we can use a
procedure similar to the one used in section&nbsp;<a href="book-Z-H-10.html#%_sec_1.1.7">1.1.7</a> for
computing square roots:<a name="call_footnote_Temp_104" href="#footnote_Temp_104"><sup><small>55</small></sup></a><p>

<p><p><tt>(define&nbsp;(close-enough?&nbsp;x&nbsp;y)<br>
&nbsp;&nbsp;(&lt;&nbsp;(abs&nbsp;(-&nbsp;x&nbsp;y))&nbsp;0.001))<br>
</tt><p><p><p>

<tt>Search</tt> is awkward to use directly, because
we can accidentally give it points at which <em>f</em>'s
values do not have the required sign, in which case we get a wrong answer.
Instead we will use <tt>search</tt> via the following procedure, which
checks to see which of the endpoints has a negative function value and
which has a positive value, and calls the <tt>search</tt> procedure
accordingly.  If the function has the same sign on the two given
points, the half-interval method cannot be used, in which case the
procedure signals an error.<a name="call_footnote_Temp_105" href="#footnote_Temp_105"><sup><small>56</small></sup></a><p>

<p><p><tt><a name="%_idx_1092"></a>(define&nbsp;(half-interval-method&nbsp;f&nbsp;a&nbsp;b)<br>
&nbsp;&nbsp;(let&nbsp;((a-value&nbsp;(f&nbsp;a))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(b-value&nbsp;(f&nbsp;b)))<br>
&nbsp;&nbsp;&nbsp;&nbsp;(cond&nbsp;((and&nbsp;(negative?&nbsp;a-value)&nbsp;(positive?&nbsp;b-value))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(search&nbsp;f&nbsp;a&nbsp;b))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;((and&nbsp;(negative?&nbsp;b-value)&nbsp;(positive?&nbsp;a-value))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(search&nbsp;f&nbsp;b&nbsp;a))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(else<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(error&nbsp;&quot;Values&nbsp;are&nbsp;not&nbsp;of&nbsp;opposite&nbsp;sign&quot;&nbsp;a&nbsp;b)))))<br>
</tt><p><p><p>

<a name="%_idx_1094"></a>The following example uses the half-interval method to approximate <img src="book-Z-G-D-9.gif" border="0">
as the root between 2 and 4 of <tt>sin</tt>  <em>x</em>  =  0:<p>

<p><p><tt>(half-interval-method&nbsp;sin&nbsp;2.0&nbsp;4.0)<br>
<i>3.14111328125</i><br>
</tt><p><p><p>

Here is another example, using the half-interval method
to search for a root of the equation <em>x</em><sup>3</sup>  -  2<em>x</em>  -  3  =  0
between 1 and 2:<p>

<p><p><tt>(half-interval-method&nbsp;(lambda&nbsp;(x)&nbsp;(-&nbsp;(*&nbsp;x&nbsp;x&nbsp;x)&nbsp;(*&nbsp;2&nbsp;x)&nbsp;3))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;1.0<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;2.0)<br>
<i>1.89306640625</i><br>
</tt><p><p><p>

<a name="%_sec_Temp_106"></a>
<h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_106">Finding fixed points of functions</a></h4><p>

<a name="%_idx_1096"></a><a name="%_idx_1098"></a>
A number <em>x</em> is called a <em>fixed point</em> of a function <em>f</em> if <em>x</em>
satisfies the equation <em>f</em>(<em>x</em>) = <em>x</em>.  For some functions <em>f</em> we can locate
a fixed point by beginning with an initial guess and applying <em>f</em>
repeatedly,<p>

<p><div align=left><img src="ch1-Z-G-33.gif" border="0"></div><p><p>

until the value does not change very much.  Using this idea, we can
devise a procedure <tt>fixed-point</tt> that takes as inputs a function
and an initial guess and produces an approximation to a fixed point of
the function.  We apply the function repeatedly until we find two
successive values whose difference is less than some prescribed
tolerance:<p>


<p><p><tt>(define&nbsp;tolerance&nbsp;0.00001)<br>
<a name="%_idx_1100"></a>(define&nbsp;(fixed-point&nbsp;f&nbsp;first-guess)<br>
&nbsp;&nbsp;(define&nbsp;(close-enough?&nbsp;v1&nbsp;v2)<br>
&nbsp;&nbsp;&nbsp;&nbsp;(&lt;&nbsp;(abs&nbsp;(-&nbsp;v1&nbsp;v2))&nbsp;tolerance))<br>
&nbsp;&nbsp;(define&nbsp;(try&nbsp;guess)<br>
&nbsp;&nbsp;&nbsp;&nbsp;(let&nbsp;((next&nbsp;(f&nbsp;guess)))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(if&nbsp;(close-enough?&nbsp;guess&nbsp;next)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;next<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(try&nbsp;next))))<br>
&nbsp;&nbsp;(try&nbsp;first-guess))<br>
</tt><p><p>
<a name="%_idx_1102"></a><a name="%_idx_1104"></a>For example, we can use this method to approximate the fixed point of
the cosine function, starting with 1 as an initial approximation:<a name="call_footnote_Temp_107" href="#footnote_Temp_107"><sup><small>57</small></sup></a><p>


<p><p><tt><a name="%_idx_1112"></a><a name="%_idx_1114"></a>(fixed-point&nbsp;cos&nbsp;1.0)<br>
<i>.7390822985224023</i><br>
</tt><p><p>
Similarly, we can find a solution to the equation
<em>y</em> = <tt>sin</tt> <em>y</em>  +  <tt>cos</tt> <em>y</em>:<p>


<p><p><tt><a name="%_idx_1116"></a><a name="%_idx_1118"></a>(fixed-point&nbsp;(lambda&nbsp;(y)&nbsp;(+&nbsp;(sin&nbsp;y)&nbsp;(cos&nbsp;y)))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;1.0)<br>
<i>1.2587315962971173</i><br>
</tt><p><p><p>


The fixed-point process is reminiscent of the process we used for
finding square roots in section&nbsp;<a href="book-Z-H-10.html#%_sec_1.1.7">1.1.7</a>.  Both are based on the
idea of repeatedly improving a guess until the result satisfies some
criterion.  In fact, we can readily formulate the <a name="%_idx_1120"></a>square-root
computation as a fixed-point search.  Computing the square root of
some number <em>x</em> requires finding a <em>y</em> such that <em>y</em><sup>2</sup>  =  <em>x</em>.  Putting
this equation into the equivalent form <em>y</em>  =  <em>x</em>/<em>y</em>, we recognize that we
are looking for a fixed point of the function<a name="call_footnote_Temp_108" href="#footnote_Temp_108"><sup><small>58</small></sup></a> <em>y</em>  <img src="book-Z-G-D-17.gif" border="0">  <em>x</em>/<em>y</em>, and we
can therefore try to compute square roots as<p>


<p><p><tt>(define&nbsp;(sqrt&nbsp;x)<br>
&nbsp;&nbsp;(fixed-point&nbsp;(lambda&nbsp;(y)&nbsp;(/&nbsp;x&nbsp;y))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;1.0))<br>
</tt><p><p><p>

Unfortunately, this fixed-point search does not converge.  Consider an
initial guess <em>y</em><sub>1</sub>.  The next guess is <em>y</em><sub>2</sub>  =  <em>x</em>/<em>y</em><sub>1</sub> and the next
guess is <em>y</em><sub>3</sub>  =  <em>x</em>/<em>y</em><sub>2</sub>  =  <em>x</em>/(<em>x</em>/<em>y</em><sub>1</sub>)  =  <em>y</em><sub>1</sub>.  This results in an infinite
loop in which the two guesses <em>y</em><sub>1</sub> and <em>y</em><sub>2</sub> repeat over and over,
oscillating about the answer.<p>

One way to control such oscillations is to prevent the guesses from
changing so much.
Since the answer is always between our guess <em>y</em>
and <em>x</em>/<em>y</em>, we can make a new guess that is not as far from <em>y</em> as <em>x</em>/<em>y</em>
by averaging <em>y</em> with <em>x</em>/<em>y</em>, so that the next guess after
<em>y</em> is (1/2)(<em>y</em> + <em>x</em>/<em>y</em>) instead of <em>x</em>/<em>y</em>.
The process of making such a sequence of guesses is simply the process
of looking for a fixed point of <em>y</em>  <img src="book-Z-G-D-17.gif" border="0">  (1/2)(<em>y</em> + <em>x</em>/<em>y</em>):<p>

<p><p><tt><a name="%_idx_1126"></a>(define&nbsp;(sqrt&nbsp;x)<br>
&nbsp;&nbsp;(fixed-point&nbsp;(lambda&nbsp;(y)&nbsp;(average&nbsp;y&nbsp;(/&nbsp;x&nbsp;y)))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;1.0))<br>
</tt><p><p>
(Note that <em>y</em> = (1/2)(<em>y</em> + <em>x</em>/<em>y</em>) is a simple transformation of the
equation <em>y</em> = <em>x</em>/<em>y</em>; to derive it, add <em>y</em> to both sides of the equation
and divide by&nbsp;2.)<p>

With this modification, the square-root procedure works.  In fact, if
we unravel the definitions, we can see that the sequence of
approximations to the square root generated here is precisely the
same as the one generated by our original square-root procedure of
section&nbsp;<a href="book-Z-H-10.html#%_sec_1.1.7">1.1.7</a>.  This approach of averaging
successive approximations to a solution, a technique we that we call
<a name="%_idx_1128"></a><em>average damping</em>, often aids the convergence of fixed-point
searches.<p>

<p><a name="%_thm_1.35"></a>
<b>Exercise 1.35.</b>&nbsp;&nbsp;<a name="%_idx_1130"></a><a name="%_idx_1132"></a>Show that the golden ratio <img src="book-Z-G-D-11.gif" border="0"> (section&nbsp;<a href="book-Z-H-11.html#%_sec_1.2.2">1.2.2</a>)
is a fixed point of the transformation <em>x</em>  <img src="book-Z-G-D-17.gif" border="0">  1  +  1/<em>x</em>, and use
this fact to compute <img src="book-Z-G-D-11.gif" border="0"> by means of the <tt>fixed-point</tt>
procedure.
<p><p>

<p><a name="%_thm_1.36"></a>
<b>Exercise 1.36.</b>&nbsp;&nbsp;Modify <tt>fixed-point</tt> so that it prints the sequence of
approximations it generates, using
the <tt>newline</tt> and <tt>display</tt> primitives shown in
exercise&nbsp;<a href="book-Z-H-11.html#%_thm_1.22">1.22</a>.  Then find a solution to <em>x</em><sup><em>x</em></sup>  = 
1000 by finding a fixed point of <em>x</em>  <img src="book-Z-G-D-17.gif" border="0">  <tt>log</tt>(1000)/<tt>log</tt>(<em>x</em>).  (Use
Scheme's <a name="%_idx_1134"></a><a name="%_idx_1136"></a>primitive <tt>log</tt> procedure, which computes natural
logarithms.)  Compare the number of steps this takes with and without
average damping.  (Note that you cannot start <tt>fixed-point</tt> with a
guess of 1, as this would cause division by <tt>log</tt>(1) = 0.)

<p><p>

<p><a name="%_thm_1.37"></a>
<b>Exercise 1.37.</b>&nbsp;&nbsp;<a name="%_idx_1138"></a>a. An infinite <em>continued fraction</em> is an expression of the form
<p><div align=left><img src="ch1-Z-G-34.gif" border="0"></div><p> 
<a name="%_idx_1140"></a><a name="%_idx_1142"></a>As an example, one can show that the infinite continued fraction
expansion with the <em>N</em><sub><em>i</em></sub> and the <em>D</em><sub><em>i</em></sub> all equal to 1 produces
1/<img src="book-Z-G-D-11.gif" border="0">, where <img src="book-Z-G-D-11.gif" border="0"> is the golden ratio (described in
section&nbsp;<a href="book-Z-H-11.html#%_sec_1.2.2">1.2.2</a>).
One way to approximate an
infinite continued fraction is to truncate the expansion after a given
number of terms.  Such a truncation -- a so-called <em><em>k</em>-term finite
continued fraction</em> -- has the form
<p><div align=left><img src="ch1-Z-G-35.gif" border="0"></div><p> 
Suppose that <tt>n</tt> and <tt>d</tt> are procedures of one argument (the
term index <em>i</em>) that return the <em>N</em><sub><em>i</em></sub> and <em>D</em><sub><em>i</em></sub> of the terms of the
continued fraction.  Define a procedure <tt>cont-frac</tt>
such that evaluating <tt>(cont-frac n d k)</tt>
computes the value of the <em>k</em>-term finite
continued fraction.  Check your procedure by approximating 1/<img src="book-Z-G-D-11.gif" border="0"> using
<p><p><tt>(cont-frac&nbsp;(lambda&nbsp;(i)&nbsp;1.0)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(lambda&nbsp;(i)&nbsp;1.0)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;k)<br>
</tt><p><p>
for successive values of <tt>k</tt>.  How large must you make <tt>k</tt>
in order to get an approximation that is accurate to 4 decimal places?<p>

<p><p>b. If your <tt>cont-frac</tt>
procedure generates a recursive process, write one that generates
an iterative process.
If it generates an iterative process, write one that generates
a recursive process.

<p><p>

<p><a name="%_thm_1.38"></a>
<b>Exercise 1.38.</b>&nbsp;&nbsp;<a name="%_idx_1144"></a>In 1737, the Swiss mathematician Leonhard Euler published a memoir
<em>De Fractionibus Continuis</em>, which included a <a name="%_idx_1146"></a><a name="%_idx_1148"></a>continued fraction
expansion for <em>e</em> - 2, where <em>e</em> is the base of the natural logarithms.
In this fraction, the <em>N</em><sub><em>i</em></sub> are all 1, and the <em>D</em><sub><em>i</em></sub> are successively
1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, <tt>...</tt>.  Write a program that uses
your <tt>cont-frac</tt> procedure from
exercise&nbsp;<a href="#%_thm_1.37">1.37</a> to approximate <em>e</em>, based on
Euler's expansion.
<p><p>

<p><a name="%_thm_1.39"></a>
<b>Exercise 1.39.</b>&nbsp;&nbsp;<a name="%_idx_1150"></a><a name="%_idx_1152"></a><a name="%_idx_1154"></a>A continued fraction representation of the tangent function was
published in 1770 by the German mathematician J.H. Lambert:
<p><div align=left><img src="ch1-Z-G-36.gif" border="0"></div><p> 
where <em>x</em> is in radians.
Define a procedure <tt>(tan-cf x k)</tt> that computes an approximation
to the tangent function based on Lambert's
formula.  <tt>K</tt> specifies the number of terms to compute, as in
exercise&nbsp;<a href="#%_thm_1.37">1.37</a>.
<p><p>

<a name="%_sec_1.3.4"></a>
<h3><a href="book-Z-H-4.html#%_toc_%_sec_1.3.4">1.3.4&nbsp;&nbsp;Procedures as Returned Values</a></h3><p>


<a name="%_idx_1156"></a><a name="%_idx_1158"></a>
The above examples demonstrate how
the ability to pass procedures as arguments significantly enhances
the expressive power of our programming language.  We can achieve even
more expressive power by creating procedures whose returned values are
themselves procedures.<p>

We can illustrate this idea by looking again at the fixed-point
example described at the end of
section&nbsp;<a href="#%_sec_1.3.3">1.3.3</a>.  We formulated a new version
of the square-root procedure as a fixed-point search, starting with
the observation that <img src="book-Z-G-D-13.gif" border="0"><em>x</em> is a fixed-point of the function
<em>y</em> <img src="book-Z-G-D-17.gif" border="0">  <em>x</em>/<em>y</em>.  Then we used average damping to make the
approximations converge.  Average damping is a useful general
technique in itself.  Namely, given a function&nbsp;<em>f</em>, we consider the
function whose value at <em>x</em> is equal to the average of <em>x</em> and <em>f</em>(<em>x</em>).<p>


We can express the idea of average damping by means of the
following procedure:<p>

<p><p><tt><a name="%_idx_1160"></a>(define&nbsp;(average-damp&nbsp;f)<br>
&nbsp;&nbsp;(lambda&nbsp;(x)&nbsp;(average&nbsp;x&nbsp;(f&nbsp;x))))<br>
</tt><p><p>
<tt>Average-damp</tt> is a procedure that takes as its argument a
procedure <tt>f</tt> and returns as its value a procedure (produced by
the <tt>lambda</tt>) that, when applied to a number <tt>x</tt>, produces the
average of <tt>x</tt> and <tt>(f x)</tt>.  For example, applying <tt>average-damp</tt> to the <tt>square</tt> procedure produces a procedure whose
value at some number <em>x</em> is the average of <em>x</em> and <em>x</em><sup>2</sup>.  Applying
this resulting procedure to 10 returns the average of 10 and 100, or
55:<a name="call_footnote_Temp_114" href="#footnote_Temp_114"><sup><small>59</small></sup></a><p>


<p><p><tt>((average-damp&nbsp;square)&nbsp;10)<br>
<i>55</i><br>
</tt><p><p><p>

<a name="%_idx_1168"></a>Using <tt>average-damp</tt>, we can reformulate the square-root procedure
as follows:<p>


<p><p><tt><a name="%_idx_1170"></a>(define&nbsp;(sqrt&nbsp;x)<br>
&nbsp;&nbsp;(fixed-point&nbsp;(average-damp&nbsp;(lambda&nbsp;(y)&nbsp;(/&nbsp;x&nbsp;y)))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;1.0))<br>
</tt><p><p>
Notice how this formulation makes explicit the three ideas in the
method: fixed-point search, average damping, and the function
<em>y</em> <img src="book-Z-G-D-17.gif" border="0">  <em>x</em>/<em>y</em>.  It is instructive to compare this formulation of the
square-root method with the original version given in
section&nbsp;<a href="book-Z-H-10.html#%_sec_1.1.7">1.1.7</a>.  Bear in mind that these procedures express
the same process, and notice how much clearer the idea becomes when we
express the process in terms of these abstractions.  In general, there
are many ways to formulate a process as a procedure.  Experienced
programmers know how to choose procedural formulations that are
particularly perspicuous, and where useful elements of the process are
exposed as separate entities that can be reused in other applications.
As a simple example of reuse, notice that the cube root of <em>x</em> is a
fixed point of the function <em>y</em> <img src="book-Z-G-D-17.gif" border="0">  <em>x</em>/<em>y</em><sup>2</sup>, so we can immediately
generalize our square-root procedure to one that extracts <a name="%_idx_1172"></a><a name="%_idx_1174"></a>cube
roots:<a name="call_footnote_Temp_115" href="#footnote_Temp_115"><sup><small>60</small></sup></a><p>


<p><p><tt><a name="%_idx_1176"></a>(define&nbsp;(cube-root&nbsp;x)<br>
&nbsp;&nbsp;(fixed-point&nbsp;(average-damp&nbsp;(lambda&nbsp;(y)&nbsp;(/&nbsp;x&nbsp;(square&nbsp;y))))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;1.0))<br>
</tt><p><p><p>


<a name="%_sec_Temp_116"></a>
<h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_116">Newton's method</a></h4><p>

<a name="%_idx_1178"></a>
When we first introduced the square-root procedure, in
section&nbsp;<a href="book-Z-H-10.html#%_sec_1.1.7">1.1.7</a>, we mentioned that this was a special case of
<em>Newton's method</em>.  
If <em>x</em> <img src="book-Z-G-D-17.gif" border="0">  <em>g</em>(<em>x</em>) is a differentiable function, then a solution of
the equation <em>g</em>(<em>x</em>) = 0 is a fixed point of the function <em>x</em> <img src="book-Z-G-D-17.gif" border="0">  <em>f</em>(<em>x</em>)
where
<p><div align=left><img src="ch1-Z-G-37.gif" border="0"></div><p>
and
<em>D</em><em>g</em>(<em>x</em>) is the derivative of <em>g</em> evaluated at <em>x</em>.  <a name="%_idx_1180"></a>Newton's
method is the use of the fixed-point method we saw above to
approximate a solution of the equation by finding a fixed point of
the function <em>f</em>.<a name="call_footnote_Temp_117" href="#footnote_Temp_117"><sup><small>61</small></sup></a>
For many functions <em>g</em> and for sufficiently good initial guesses for
<em>x</em>, Newton's method converges very rapidly to a solution of
<em>g</em>(<em>x</em>) = 0.<a name="call_footnote_Temp_118" href="#footnote_Temp_118"><sup><small>62</small></sup></a><p>

<a name="%_idx_1186"></a><a name="%_idx_1188"></a><a name="%_idx_1190"></a>In order to implement Newton's method as a procedure, we must first
express the idea of derivative.  Note that ``derivative,'' like
average damping, is something that transforms a function into another
function.  For instance, the derivative of the function <em>x</em> <img src="book-Z-G-D-17.gif" border="0"> 
<em>x</em><sup>3</sup> is the function <em>x</em>  <img src="book-Z-G-D-17.gif" border="0">  3<em>x</em><sup>2</sup>.  In general, if <em>g</em> is a
function and <em>d</em><em>x</em> is a small number, then the derivative <em>D</em><em>g</em> of <em>g</em> is
the function whose value at any number <em>x</em> is given (in the limit of
small <em>d</em><em>x</em>) by
<p><div align=left><img src="ch1-Z-G-38.gif" border="0"></div><p>
Thus, we can express the idea of derivative (taking <em>d</em><em>x</em> to be, say,
0.00001) as the procedure<p>

<p><p><tt><a name="%_idx_1192"></a>(define&nbsp;(deriv&nbsp;g)<br>
&nbsp;&nbsp;(lambda&nbsp;(x)<br>
&nbsp;&nbsp;&nbsp;&nbsp;(/&nbsp;(-&nbsp;(g&nbsp;(+&nbsp;x&nbsp;dx))&nbsp;(g&nbsp;x))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;dx)))<br>
</tt><p><p>
along with the definition<p>

<p><p><tt>(define&nbsp;dx&nbsp;0.00001)<br>
</tt><p><p><p>

Like <tt>average-damp</tt>, <tt>deriv</tt> is a procedure that takes a
procedure as argument and returns a procedure as value.  For example,
to approximate the derivative of <em>x</em>  <img src="book-Z-G-D-17.gif" border="0">  <em>x</em><sup>3</sup> at 5 (whose exact
value is 75) we can evaluate<p>

<p><p><tt><a name="%_idx_1194"></a>(define&nbsp;(cube&nbsp;x)&nbsp;(*&nbsp;x&nbsp;x&nbsp;x))<br>
((deriv&nbsp;cube)&nbsp;5)<br>
<i>75.00014999664018</i><br>
</tt><p><p><p>

With the aid of <tt>deriv</tt>, we can express Newton's method as a
fixed-point process:<p>

<p><p><tt><a name="%_idx_1196"></a>(define&nbsp;(newton-transform&nbsp;g)<br>
&nbsp;&nbsp;(lambda&nbsp;(x)<br>
&nbsp;&nbsp;&nbsp;&nbsp;(-&nbsp;x&nbsp;(/&nbsp;(g&nbsp;x)&nbsp;((deriv&nbsp;g)&nbsp;x)))))<br>
<a name="%_idx_1198"></a>(define&nbsp;(newtons-method&nbsp;g&nbsp;guess)<br>
&nbsp;&nbsp;(fixed-point&nbsp;(newton-transform&nbsp;g)&nbsp;guess))<br>
</tt><p><p>
The <tt>newton-transform</tt> procedure expresses the formula at the
beginning of this section, and <tt>newtons-method</tt> is readily defined
in terms of this.  It takes as arguments a procedure that computes the
function for which we want to find a zero, together with an initial
guess.  For instance, to find the <a name="%_idx_1200"></a>square root of <em>x</em>, we can use
Newton's method to find a zero of the function <em>y</em> <img src="book-Z-G-D-17.gif" border="0">  <em>y</em><sup>2</sup> - <em>x</em> starting with
an initial guess of 1.<a name="call_footnote_Temp_119" href="#footnote_Temp_119"><sup><small>63</small></sup></a>
This provides yet another form of the square-root
procedure:<p>

<p><p><tt><a name="%_idx_1202"></a>(define&nbsp;(sqrt&nbsp;x)<br>
&nbsp;&nbsp;(newtons-method&nbsp;(lambda&nbsp;(y)&nbsp;(-&nbsp;(square&nbsp;y)&nbsp;x))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;1.0))<br>
</tt><p><p><p>

<a name="%_sec_Temp_120"></a>
<h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_120">Abstractions and first-class procedures</a></h4><p>

We've seen two ways to express the square-root
computation as an instance of a more general method, once as a fixed-point
search and once using Newton's method.  Since Newton's method
was itself expressed as a fixed-point process,
we actually saw two ways to compute square roots as fixed points.
Each method begins with a function and finds a <a name="%_idx_1204"></a>fixed
point of some transformation of the function.  We can express this
general idea itself as a procedure:<p>

<p><p><tt><a name="%_idx_1206"></a>(define&nbsp;(fixed-point-of-transform&nbsp;g&nbsp;transform&nbsp;guess)<br>
&nbsp;&nbsp;(fixed-point&nbsp;(transform&nbsp;g)&nbsp;guess))<br>
</tt><p><p>
This very general procedure takes as its arguments a procedure <tt>g</tt>
that computes some function, a procedure that transforms <tt>g</tt>, and
an initial guess.  The returned result is a fixed point of the
transformed function.<p>

<a name="%_idx_1208"></a>Using this abstraction, we can recast the first square-root
computation from this section (where we look for
a fixed point of the average-damped version of <em>y</em>  <img src="book-Z-G-D-17.gif" border="0">  <em>x</em>/<em>y</em>)
as an instance of this general method:<p>

<p><p><tt><a name="%_idx_1210"></a>(define&nbsp;(sqrt&nbsp;x)<br>
&nbsp;&nbsp;(fixed-point-of-transform&nbsp;(lambda&nbsp;(y)&nbsp;(/&nbsp;x&nbsp;y))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;average-damp<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;1.0))<br>
</tt><p><p>
<a name="%_idx_1212"></a>Similarly, we can express the second square-root computation from this section
(an instance
of Newton's method that finds a fixed point of the
Newton transform of <em>y</em> <img src="book-Z-G-D-17.gif" border="0">  <em>y</em><sup>2</sup> - <em>x</em>) as<p>

<p><p><tt><a name="%_idx_1214"></a><a name="%_idx_1216"></a>(define&nbsp;(sqrt&nbsp;x)<br>
&nbsp;&nbsp;(fixed-point-of-transform&nbsp;(lambda&nbsp;(y)&nbsp;(-&nbsp;(square&nbsp;y)&nbsp;x))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;newton-transform<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;1.0))<br>
</tt><p><p><p>

We began section&nbsp;<a href="#%_sec_1.3">1.3</a> with the observation
that compound procedures
are a crucial abstraction mechanism, because they permit us to
express general methods of computing as explicit elements in our
programming language.  Now we've seen how higher-order
procedures permit us to manipulate these general methods
to create further abstractions.<p>

As programmers, we should be alert to opportunities to identify the
underlying abstractions in our programs and to build upon them and
generalize them to create more powerful abstractions.  This is not to
say that one should always write programs in the most abstract way
possible; expert programmers know how to choose the level of
abstraction appropriate to their task.  But it is important to be able
to think in terms of these abstractions, so that we can be ready to
apply them in new contexts.  The significance of higher-order
procedures is that they enable us to represent these abstractions
explicitly as elements in our programming language, so that they can
be handled just like other computational elements.<p>

In general, programming languages impose restrictions on the ways in
which computational elements can be manipulated.  Elements with the
fewest restrictions are said to have <a name="%_idx_1218"></a><em>first-class</em> status.  Some
of the ``rights and privileges'' of first-class elements are:<a name="call_footnote_Temp_121" href="#footnote_Temp_121"><sup><small>64</small></sup></a>
<p><ul>
<li>They may be named by variables.
<li>They may be passed as arguments to procedures.
<li>They may be returned as the results of procedures.
<li>They may be included in data structures.<a name="call_footnote_Temp_122" href="#footnote_Temp_122"><sup><small>65</small></sup></a>
</ul><p>
<a name="%_idx_1222"></a><a name="%_idx_1224"></a>Lisp, unlike other common programming languages, awards procedures
full first-class status.  This poses challenges for efficient
implementation, but the resulting gain in expressive power is
enormous.<a name="call_footnote_Temp_123" href="#footnote_Temp_123"><sup><small>66</small></sup></a><p>

<p><a name="%_thm_1.40"></a>
<b>Exercise 1.40.</b>&nbsp;&nbsp;Define a procedure <tt>cubic</tt> that can be used together with the <tt>newtons-method</tt> procedure in expressions of the form<p>


<p><p><tt>(newtons-method&nbsp;(cubic&nbsp;a&nbsp;b&nbsp;c)&nbsp;1)<br>
</tt><p><p>
to approximate zeros of the cubic <em>x</em><sup>3</sup>  + <em>a</em><em>x</em><sup>2</sup>  + <em>b</em><em>x</em>  + <em>c</em>.
<p><p>

<p><a name="%_thm_1.41"></a>
<b>Exercise 1.41.</b>&nbsp;&nbsp;Define a procedure <tt>double</tt> that takes a procedure of one
argument as argument and
returns a procedure that applies the original procedure twice.  For
example, if <tt>inc</tt> is a procedure that adds 1 to its argument,
then <tt>(double inc)</tt> should be a procedure that adds 2.  What
value is returned by<p>


<p><p><tt>(((double&nbsp;(double&nbsp;double))&nbsp;inc)&nbsp;5)<br>
</tt><p><p>
<p><p>

<p><a name="%_thm_1.42"></a>
<b>Exercise 1.42.</b>&nbsp;&nbsp;<a name="%_idx_1226"></a><a name="%_idx_1228"></a>Let <em>f</em> and <em>g</em> be two one-argument functions.  The <em>composition</em>
<em>f</em> after <em>g</em> is defined to be the function <em>x</em> <img src="book-Z-G-D-17.gif" border="0">  <em>f</em>(<em>g</em>(<em>x</em>)).
Define a procedure <tt>compose</tt> that implements composition.  For
example, if <tt>inc</tt> is a procedure that adds 1 to its argument,

<p><p><tt>((compose&nbsp;square&nbsp;inc)&nbsp;6)<br>
<i>49</i><br>
</tt><p><p>
<p><p>


<p><a name="%_thm_1.43"></a>
<b>Exercise 1.43.</b>&nbsp;&nbsp;<a name="%_idx_1230"></a>If <em>f</em> is a numerical function and <em>n</em> is a positive integer, then we
can form the <em>n</em>th repeated application of <em>f</em>, which is defined to be
the function whose value at <em>x</em> is <em>f</em>(<em>f</em>(<tt>...</tt>(<em>f</em>(<em>x</em>))<tt>...</tt>)).  For
example, if <em>f</em> is the function <em>x</em>  <img src="book-Z-G-D-17.gif" border="0">  <em>x</em> + 1,
then the <em>n</em>th repeated application of <em>f</em> is
the function <em>x</em>  <img src="book-Z-G-D-17.gif" border="0">  <em>x</em> + <em>n</em>.  If <em>f</em> is the operation of
squaring a number, then the <em>n</em>th repeated application of <em>f</em> is the
function that raises its argument to the 2<sup><em>n</em></sup>th power.  Write a
procedure that takes as inputs a procedure that computes <em>f</em> and a
positive integer <em>n</em> and returns the procedure that computes the <em>n</em>th
repeated application of <em>f</em>.  Your procedure should be able to be used
as follows:<p>


<p><p><tt>((repeated&nbsp;square&nbsp;2)&nbsp;5)<br>
<i>625</i><br>
</tt><p><p>
Hint: You may find it convenient to use <tt>compose</tt> from
exercise&nbsp;<a href="#%_thm_1.42">1.42</a>.

<p><p>

<p><a name="%_thm_1.44"></a>
<b>Exercise 1.44.</b>&nbsp;&nbsp;<a name="%_idx_1232"></a><a name="%_idx_1234"></a><a name="%_idx_1236"></a>The idea of <em>smoothing</em> a function is an important concept in
signal processing.  If <em>f</em> is a function and <em>d</em><em>x</em> is some small number,
then the smoothed version of <em>f</em> is the function whose value at a
point <em>x</em> is the average of <em>f</em>(<em>x</em> - <em>d</em><em>x</em>), <em>f</em>(<em>x</em>), and <em>f</em>(<em>x</em> + <em>d</em><em>x</em>).  Write a
procedure <tt>smooth</tt> that takes as input a procedure that computes
<em>f</em> and returns a procedure that computes the smoothed <em>f</em>.  It is
sometimes valuable to repeatedly smooth a function (that is, smooth
the smoothed function, and so on) to obtained the <em><em>n</em>-fold
smoothed function</em>.  Show how to generate the <em>n</em>-fold smoothed
function of any given function using <tt>smooth</tt> and <tt>repeated</tt>
from exercise&nbsp;<a href="#%_thm_1.43">1.43</a>.
<p><p>

<p><a name="%_thm_1.45"></a>
<b>Exercise 1.45.</b>&nbsp;&nbsp;We saw in section&nbsp;<a href="#%_sec_1.3.3">1.3.3</a>
that attempting to compute square roots by naively finding a
fixed point of <em>y</em> <img src="book-Z-G-D-17.gif" border="0">  <em>x</em>/<em>y</em> does not converge, and that this can be
fixed by average damping.  The same method works for finding cube
roots as fixed points of the average-damped <em>y</em> <img src="book-Z-G-D-17.gif" border="0">  <em>x</em>/<em>y</em><sup>2</sup>.
Unfortunately, the process does not work for <a name="%_idx_1238"></a><a name="%_idx_1240"></a>fourth roots -- a single
average damp is not enough to make a fixed-point search for <em>y</em> <img src="book-Z-G-D-17.gif" border="0"> 
<em>x</em>/<em>y</em><sup>3</sup> converge.  On the other hand, if we average damp twice (i.e.,
use the average damp of the average damp of <em>y</em> <img src="book-Z-G-D-17.gif" border="0">  <em>x</em>/<em>y</em><sup>3</sup>) the
fixed-point search does converge.  Do some experiments to determine
how many average damps are required to compute <a name="%_idx_1242"></a><a name="%_idx_1244"></a><em>n</em>th roots as a
fixed-point search based upon repeated average damping of <em>y</em> <img src="book-Z-G-D-17.gif" border="0"> 
<em>x</em>/<em>y</em><sup><em>n</em>-1</sup>.  Use this to implement a simple procedure for computing
<em>n</em>th roots using <tt>fixed-point</tt>, <tt>average-damp</tt>, and the <tt>repeated</tt> procedure of exercise&nbsp;<a href="#%_thm_1.43">1.43</a>.
Assume that any arithmetic operations you need are available as primitives.

<p><p>

<p><a name="%_thm_1.46"></a>
<b>Exercise 1.46.</b>&nbsp;&nbsp;<a name="%_idx_1246"></a><a name="%_idx_1248"></a><a name="%_idx_1250"></a><a name="%_idx_1252"></a>Several of the numerical methods described in this chapter are instances
of an extremely general computational strategy known as <em>iterative
improvement</em>.  Iterative improvement says that, to compute something,
we start with an initial guess for the answer, test if the guess is
good enough, and otherwise improve the guess and continue the process
using the improved guess as the new guess.  Write a procedure <tt>iterative-improve</tt> that takes two procedures as arguments: a method
for telling whether a guess is good enough and a method for improving
a guess.  <tt>Iterative-improve</tt> should return as its value a
procedure that takes a guess as argument and keeps improving the guess
until it is good enough.  Rewrite the <tt>sqrt</tt> procedure of
section&nbsp;<a href="book-Z-H-10.html#%_sec_1.1.7">1.1.7</a> and the <tt>fixed-point</tt> procedure of
section&nbsp;<a href="#%_sec_1.3.3">1.3.3</a> in terms of <tt>iterative-improve</tt>.
<p>
<p>


<p><div class=smallprint><hr></div><p>
<div class=footnote><p><a name="footnote_Temp_90" href="#call_footnote_Temp_90"><sup><small>49</small></sup></a> This series,
<a name="%_idx_974"></a><a name="%_idx_976"></a>usually written in the equivalent form (<img src="book-Z-G-D-9.gif" border="0">/4)  =  1 - (1/3) + (1/5) - (1/7) + <tt>&middot;&middot;&middot;</tt>, is due to Leibniz.  We'll see how
to use this as the basis for some fancy numerical tricks in
section&nbsp;<a href="book-Z-H-24.html#%_sec_3.5.3">3.5.3</a>.

<p><a name="footnote_Temp_91" href="#call_footnote_Temp_91"><sup><small>50</small></sup></a> Notice
that we have used block structure (section&nbsp;<a href="book-Z-H-10.html#%_sec_1.1.8">1.1.8</a>) to
embed the definitions of <tt>pi-next</tt> and <tt>pi-term</tt> within <tt>pi-sum</tt>, since these procedures are unlikely to be useful for any
other purpose.  We will see how to get rid of them altogether in
section&nbsp;<a href="#%_sec_1.3.2">1.3.2</a>.

<p><a name="footnote_Temp_95" href="#call_footnote_Temp_95"><sup><small>51</small></sup></a> The intent of
exercises&nbsp;<a href="#%_thm_1.31">1.31</a>-<a href="#%_thm_1.33">1.33</a> is to
demonstrate the expressive power that is attained by using an
appropriate abstraction to consolidate many seemingly disparate
operations.  However, though accumulation and filtering are elegant
ideas, our hands are somewhat tied in using them at this point since
we do not yet have data structures to provide suitable means of
combination for these abstractions.  We will return to these ideas in
section&nbsp;<a href="book-Z-H-15.html#%_sec_2.2.3">2.2.3</a> when we show how
to use <em>sequences</em> as interfaces for combining filters and
accumulators to build even more powerful abstractions.  We will see
there how these methods really come into their own as a powerful and
elegant approach to designing programs.

<p><a name="footnote_Temp_96" href="#call_footnote_Temp_96"><sup><small>52</small></sup></a> This formula was discovered by the seventeenth-century
<a name="%_idx_1016"></a>English mathematician John Wallis.

<p><a name="footnote_Temp_99" href="#call_footnote_Temp_99"><sup><small>53</small></sup></a> It would be clearer and less intimidating to
people learning Lisp if a name more obvious than <tt>lambda</tt>, such as
<tt>make-procedure</tt>, were used.  But the convention is firmly
entrenched.  The notation is adopted from the <a name="%_idx_1054"></a><img src="book-Z-G-D-6.gif" border="0"> calculus, a
<a name="%_idx_1056"></a>mathematical formalism introduced by the mathematical logician Alonzo
Church (1941).  Church developed the <img src="book-Z-G-D-6.gif" border="0"> calculus to provide a
rigorous foundation for studying the notions of function and function
application.  The <img src="book-Z-G-D-6.gif" border="0"> calculus has become a basic tool for
mathematical investigations of the semantics of programming
languages.

<p><a name="footnote_Temp_101" href="#call_footnote_Temp_101"><sup><small>54</small></sup></a> Understanding internal definitions well enough to be sure a
program means what we intend it to mean requires a more elaborate
model of the evaluation process than we have presented in this
chapter.  The subtleties do not arise with internal definitions of
procedures, however.  We will return to this issue in
section&nbsp;<a href="book-Z-H-26.html#%_sec_4.1.6">4.1.6</a>, after we learn more about
evaluation.

<p><a name="footnote_Temp_104" href="#call_footnote_Temp_104"><sup><small>55</small></sup></a> We have used 0.001 as a representative ``small'' number to indicate a
tolerance for the acceptable error in a calculation.  The appropriate
tolerance for a real calculation depends upon the problem to be solved
and the limitations of the computer and the algorithm.  This is often
<a name="%_idx_1086"></a>a very subtle consideration, requiring help from a numerical analyst
or some other kind of magician.

<p><a name="footnote_Temp_105" href="#call_footnote_Temp_105"><sup><small>56</small></sup></a> This
<a name="%_idx_1088"></a><a name="%_idx_1090"></a>can be accomplished using <tt>error</tt>, which takes as
arguments a number of items that are printed as error
messages.

<p><a name="footnote_Temp_107" href="#call_footnote_Temp_107"><sup><small>57</small></sup></a> Try this during a boring lecture: Set your calculator to
<a name="%_idx_1106"></a><a name="%_idx_1108"></a><a name="%_idx_1110"></a>radians mode and then repeatedly press the <tt>cos</tt> button until you
obtain the fixed point.

<p><a name="footnote_Temp_108" href="#call_footnote_Temp_108"><sup><small>58</small></sup></a>  <img src="book-Z-G-D-17.gif" border="0"> 
<a name="%_idx_1122"></a><a name="%_idx_1124"></a>(pronounced ``maps to'') is
the mathematician's way of writing <tt>lambda</tt>.
<em>y</em>  <img src="book-Z-G-D-17.gif" border="0">  <em>x</em>/<em>y</em> means <tt>(lambda(y) (/ x y))</tt>, that is, the
function whose value at <em>y</em> is <em>x</em>/<em>y</em>.

<p><a name="footnote_Temp_114" href="#call_footnote_Temp_114"><sup><small>59</small></sup></a> Observe that this is a combination whose operator is itself
<a name="%_idx_1162"></a><a name="%_idx_1164"></a><a name="%_idx_1166"></a>a combination.  Exercise&nbsp;<a href="book-Z-H-10.html#%_thm_1.4">1.4</a> already demonstrated
the ability to form such combinations, but that was only a toy
example.  Here we begin to see the real need for such
combinations -- when applying a procedure that is obtained as the value
returned by a higher-order procedure.

<p><a name="footnote_Temp_115" href="#call_footnote_Temp_115"><sup><small>60</small></sup></a> See exercise&nbsp;<a href="#%_thm_1.45">1.45</a> for a further
generalization.

<p><a name="footnote_Temp_117" href="#call_footnote_Temp_117"><sup><small>61</small></sup></a> Elementary calculus books usually describe Newton's
method in terms of the sequence of approximations
<em>x</em><sub><em>n</em>+1</sub> = <em>x</em><sub><em>n</em></sub> - <em>g</em>(<em>x</em><sub><em>n</em></sub>)/<em>D</em><em>g</em>(<em>x</em><sub><em>n</em></sub>).  Having language for talking about
processes and using the idea of fixed points simplifies the description
of the method.

<p><a name="footnote_Temp_118" href="#call_footnote_Temp_118"><sup><small>62</small></sup></a> Newton's method does not always converge to an answer, but
it can be shown that in favorable cases each iteration doubles the
number-of-digits accuracy of the approximation to the solution.
In such cases, <a name="%_idx_1182"></a><a name="%_idx_1184"></a>Newton's method will converge much more
rapidly than the half-interval method.

<p><a name="footnote_Temp_119" href="#call_footnote_Temp_119"><sup><small>63</small></sup></a> For finding square roots, Newton's method converges rapidly to the
correct solution from any starting point.

<p><a name="footnote_Temp_121" href="#call_footnote_Temp_121"><sup><small>64</small></sup></a> The notion of first-class status of programming-language
<a name="%_idx_1220"></a>elements is due to the British computer scientist Christopher
Strachey (1916-1975).

<p><a name="footnote_Temp_122" href="#call_footnote_Temp_122"><sup><small>65</small></sup></a> We'll see
examples of this after we introduce data structures in chapter&nbsp;2.

<p><a name="footnote_Temp_123" href="#call_footnote_Temp_123"><sup><small>66</small></sup></a> The major implementation cost of first-class
procedures is that allowing procedures to be returned as values
requires reserving storage for a procedure's free variables even while
the procedure is not executing.  In the Scheme implementation we will
study in section&nbsp;<a href="book-Z-H-26.html#%_sec_4.1">4.1</a>, these variables are stored in the
procedure's environment.

</div>

<p><div class=navigation>[Go to <span><a href="book.html">first</a>, <a href="book-Z-H-11.html">previous</a></span><span>, <a href="book-Z-H-13.html">next</a></span> page<span>; &nbsp;&nbsp;</span><span><a href="book-Z-H-4.html#%_toc_start">contents</a></span><span><span>; &nbsp;&nbsp;</span><a href="book-Z-H-38.html#%_index_start">index</a></span>]</div><p>

</body>
</html>
